#pragma once


#include <string.h>
#include <string>
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <stdbool.h>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>
#include <unistd.h>
#include <random>
#include <chrono>
#include <cmath>
#include <ctime>
#include <unordered_set>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <stdexcept>
using namespace std;


// 存储文件
static const char *filename = "./Data.txt";
static const char *school_route_tsp_map = "./Data_Tsp.txt";
static const char *school_route_tsp_output = "./Data_Tsp_Output.txt";
static const char *berlin_tsp_map = "./berlin52.txt";
static const char *berlin_tsp_map_output = "./berlin52_output.txt";

// 数据类型
typedef pair<int, int> Pair;
typedef int DataType;
typedef int XYType;
typedef char NameType;
typedef char IntroType;

// 宏定义
#define MAX 9999     // 无道路==>无穷大
#define MVNum 20     // 最大地点数
#define Unit 200     // 坐标系单元长度
#define IntroLen 800 // 简介长度
#define NameLen 20

// 菜单选项
enum Input
{
    EXIT,
    ADDVex,
    ADDArc,
    DELVex,
    DELArc,
    SEARCHVex,
    SEARCHArc,
    MODIFYVex,
    MODIFYArc,
    SHOWVex,
    SHOWArc,
    SHOWMap,
    SHOWMatrix,
    CLEARMap,
    SHOWPath,
    CLEARArc,
    LAYCIRCUIT,
    PASSALLVexPath,
    PASSALLVexLoop,
    TSP_Berlin
};

// 顶点信息
typedef struct Location
{
    NameType name[NameLen];
    XYType x, y;
    IntroType intro[IntroLen];
} Location;

// 地图信息
typedef struct Campus_Route
{
    DataType vexnum;
    Location vexs[MVNum];
    DataType arcs[MVNum][MVNum];
    DataType arcnum;
} Map;

// tsp
class TSPSolver {
    private:
        int cityNum;
        std::vector<double> xCoordinates;
        std::vector<double> yCoordinates;
        std::vector<std::vector<int>> distanceMatrix;
        std::vector<int> currentRoute;
        std::vector<int> nextRoute;
        std::vector<int> minRoute;
        std::vector<int> currentArray;
        std::vector<int> nextArray;
        double currentRouteLength;
        double minRouteLength;
        std::mt19937 rng;
    
        void readInput(const std::string& inputFile) {
            std::ifstream inFile(inputFile);
            if (!inFile) {
                throw std::runtime_error("Cannot open input file.");
            }
            inFile >> cityNum;
            xCoordinates.resize(cityNum + 1);
            yCoordinates.resize(cityNum + 1);
            for (int i = 1; i <= cityNum; ++i) {
                int index;
                inFile >> index >> xCoordinates[i] >> yCoordinates[i];
            }
            inFile.close();
        }
    
        void computeDistanceMatrix() {
            distanceMatrix.resize(cityNum + 1, std::vector<int>(cityNum + 1));
            for (int i = 1; i <= cityNum; ++i) {
                for (int j = 1; j <= cityNum; ++j) {
                    double dx = xCoordinates[i] - xCoordinates[j];
                    double dy = yCoordinates[i] - yCoordinates[j];
                    distanceMatrix[i][j] = static_cast<int>(0.5 + std::hypot(dx, dy));
                }
            }
        }
    
        void constructRouteFromArray(const std::vector<int>& array, std::vector<int>& route, double& length) {
            route.clear();
            route.resize(cityNum + 1);
            route[1] = array[1];
            route[2] = array[2];
            route[3] = array[3];
            int currentSize = 3;
    
            for (int p = 4; p <= cityNum; ++p) {
                int city = array[p];
                int bestPos = 1;
                double bestIncrease = std::numeric_limits<double>::max();
    
                for (int i = 1; i <= currentSize; ++i) {
                    int next = (i % currentSize) + 1;
                    int prevCity = route[i];
                    int nextCity = route[next];
                    double increase = distanceMatrix[prevCity][city] 
                                    + distanceMatrix[city][nextCity] 
                                    - distanceMatrix[prevCity][nextCity];
    
                    if (increase < bestIncrease) {
                        bestIncrease = increase;
                        bestPos = i;
                    }
                }
    
                if (bestPos == currentSize) {
                    route[++currentSize] = city;
                } else {
                    for (int j = currentSize; j > bestPos; --j) {
                        route[j + 1] = route[j];
                    }
                    route[bestPos + 1] = city;
                    ++currentSize;
                }
            }
    
            length = 0;
            for (int i = 1; i < cityNum; ++i) {
                length += distanceMatrix[route[i]][route[i + 1]];
            }
            length += distanceMatrix[route[cityNum]][route[1]];
        }
    
        void generateInitialSolution() {
            currentArray.resize(cityNum + 1);
            std::vector<int> cities(cityNum);
            std::iota(cities.begin(), cities.end(), 1);
            std::shuffle(cities.begin(), cities.end(), rng);
    
            for (int i = 1; i <= cityNum; ++i) {
                currentArray[i] = cities[i - 1];
            }
    
            constructRouteFromArray(currentArray, currentRoute, currentRouteLength);
            minRoute = currentRoute;
            minRouteLength = currentRouteLength;
        }
    
        bool tryMove(int oldPos, int newPos) {
            nextArray = currentArray;
            if (oldPos < newPos) {
                int temp = nextArray[oldPos];
                for (int i = oldPos; i < newPos; ++i) {
                    nextArray[i] = nextArray[i + 1];
                }
                nextArray[newPos] = temp;
            } else {
                int temp = nextArray[oldPos];
                for (int i = oldPos; i > newPos; --i) {
                    nextArray[i] = nextArray[i - 1];
                }
                nextArray[newPos] = temp;
            }
    
            double newLength;
            std::vector<int> tempRoute;
            constructRouteFromArray(nextArray, tempRoute, newLength);
    
            if (newLength < currentRouteLength) {
                currentArray = nextArray;
                currentRoute = tempRoute;
                currentRouteLength = newLength;
                if (newLength < minRouteLength) {
                    minRoute = currentRoute;
                    minRouteLength = newLength;
                    std::cout << "New minimal route length: " << minRouteLength << std::endl;
                }
                return true;
            }
            return false;
        }
    
        bool trySwap(int pos1, int pos2) {
            nextArray = currentArray;
            std::swap(nextArray[pos1], nextArray[pos2]);
    
            double newLength;
            std::vector<int> tempRoute;
            constructRouteFromArray(nextArray, tempRoute, newLength);
    
            if (newLength < currentRouteLength) {
                currentArray = nextArray;
                currentRoute = tempRoute;
                currentRouteLength = newLength;
                if (newLength < minRouteLength) {
                    minRoute = currentRoute;
                    minRouteLength = newLength;
                    std::cout << "New minimal route length: " << minRouteLength << std::endl;
                }
                return true;
            }
            return false;
        }
    
    public:
        TSPSolver(const std::string& inputFile) : rng(std::random_device{}()) {
            readInput(inputFile);
            computeDistanceMatrix();
            currentRoute.resize(cityNum + 1);
            nextRoute.resize(cityNum + 1);
            minRoute.resize(cityNum + 1);
            currentArray.resize(cityNum + 1);
            nextArray.resize(cityNum + 1);
        }
    
        void solve() {
            generateInitialSolution();
            bool improved;
            do {
                improved = false;
                // Try all possible moves
                for (int oldPos = 1; oldPos <= cityNum; ++oldPos) {
                    for (int newPos = 1; newPos <= cityNum; ++newPos) {
                        if (oldPos == newPos) continue;
                        if (tryMove(oldPos, newPos)) {
                            improved = true;
                            goto NEXT_ITERATION;
                        }
                    }
                }
    
                // Try all possible swaps
                for (int pos1 = 1; pos1 <= cityNum; ++pos1) {
                    for (int pos2 = pos1 + 1; pos2 <= cityNum; ++pos2) {
                        if (trySwap(pos1, pos2)) {
                            improved = true;
                            goto NEXT_ITERATION;
                        }
                    }
                }
    
            NEXT_ITERATION:
                if (improved) continue;
                else break;
            } while (true);
        }
    
        void saveResult(const std::string& outputFile) {
            std::ofstream outFile(outputFile);
            if (!outFile) {
                throw std::runtime_error("Cannot open output file.");
            }
            for (int i = 1; i <= cityNum; ++i) {
                for (int j = 1; j <= cityNum; ++j) {
                    outFile << distanceMatrix[i][j] << " ";
                }
                outFile << std::endl;
            }
    
            // Save best route
            outFile << endl;
            for (int i = 1; i <= cityNum; ++i) {
                outFile << minRoute[i] << " ";
            }
            outFile << std::endl;
            outFile << "Total length: " << minRouteLength << std::endl;
            outFile.close();
        }
    };
    
// 格式化地图
void ClearMap(Map *map);

// 清除所有地点
void ClearArc(Map *map);

// 加载文件信息到地图
void LoadMap(const char *filename, Map *map);

// 初始化地图
void InitMap(const char *filename, Map *map);

// 已知两地点下标求距离[向上取整]
int CalDistance(const Map *map, const int a, const int b);

// 增加地点信息
void AddVexMap(Map *map);

// 增加道路信息
void AddArcMap(Map *map);

// 删除某个地点
void DelVexMap(Map *map);

// 删除某个道路
void DelArcMap(Map *map);

// 查找某个地点
void SearchVexMap(const Map *map);

// 查找某个道路
void SearchArcMap(const Map *map);

// 修改某个地点
void ModifyVexMap(Map *map);

// 修改某个道路
// void ModifyArcMap(Map* map);

// 打印地图中所有地点
void ShowVexMap(const Map *map);

// 打印地图中所有道路
void ShowArcMap(const Map *map);

// 打印整个地图
void ShowMap(const Map *map);

// 显示当前矩阵数据
void ShowMatrix(const Map *map);

// 计算从obj到其他所有地点的最短简单路径[递增输出]
void ShowShortest_Path(const Map *map);

// 最短通电线路(铺路规划,每条电路长度,电路总长度) ==> MST
void Lay_Circuit(const Map *map);

// A地出发经过所有点且距离最短(可重复)
void PassAllVex_Path(const Map *map);

// A地出发过所有点回到A点且距离最短(可重复)
void PassAllVex_Loop(const Map *map);

// tsp问题的单独测试
void Tsp_Berlin();

// 保存文件信息到文件
void SaveMap(const char *filename, Map *map);